package com.zyf.markAllenWeiss.sort;

import java.util.Arrays;

public class Shellsort {

	public static void main(String[] args) {
		Integer[] arr = new Integer[] { 81, 94, 11, 96, 12, 5, 17, 95, 28, 58, 41, 75, 15 };
		shellsort(arr);
		System.out.println(Arrays.toString(arr));
	}

	/**
	 * 希尔排序
	 * 
	 * @param a
	 */
	public static <AnyType extends Comparable<? super AnyType>> void shellsort(AnyType[] a) {
		int j;
		for (int gap = a.length / 2; gap > 0; gap /= 2) {
			for (int i = gap; i < a.length; i++) {
				AnyType tmp = a[i];
				for (j = i; j >= gap && tmp.compareTo(a[j - gap]) < 0; j -= gap) {
					a[j] = a[j - gap];
				}
				a[j] = tmp;
			}
		}
	}
}
